package com.masterlu.leetcode.daily.stack.simple;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 1441. 用栈操作构建数组
 * https://leetcode-cn.com/problems/build-an-array-with-stack-operations/
 */
public class S1441BuildArray {

    public List<String> buildArray(int[] target, int n) {

        List<String> strings = new ArrayList<>();

        //首先将目标数据存储在map中，方便比对
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : target) {
            map.put(i,i);
        }

        /**
         * 1.先进行push操作。检查目标数据中是否存在最新push的元素。如果不存在，则执行pop操作。
         * 2.进行下一次循环
         */
        for (int i = 1; i <= n && i <= target[target.length-1]; i++) {
            strings.add("Push");
            if (map.get(i) == null){
                strings.add("Pop");
            }

        }

        return strings;
    }

}
